<?php

namespace App\Http\Controllers\v1\algorithmAndDataStruct;

use App\Http\Controllers\Controller;
use App\services\v1\SignRecordServices;

class AlgorithmController extends Controller
{
    private $test = null;

    public function __construct()
    {
        parent::__construct();
        $this->test = [3,4,1,5,2,1,13];
        $sign = new SignRecordServices();
        $res = $sign->signMysqlAlgorithm();
        dd($res);
//        $sortRes = $this->bubblingSort($this->test);
//        $sortRes = $this->mergeSortedArray([1,2,3],[1,3,4]);
        $sortRes = $this->isPalindrome((string)12321);
        dd($sortRes);
    }

    /**
     * dichotomous 二分查找
     * @param int $key
     * @return int
     */
    public function search(int $key): int
    {
        $left  = 0;
        $right = count($this->test) - 1;
        while ($left < $right) {
            $middle = ceil($left + ($right-$left)/2);
            if ($key == $this->test[$middle]) {
                return $this->test[$middle];
            }else if($key > $this->test[$middle]) {
                $left = $middle;
            }else{
                $right = $middle;
            }
        }
        return 0;
    }

    /**
     * 快排
     * @param array $sortArr
     * @return array
     */
    public function quickSort(array $sortArr): array
    {
        $sortArrLength = count($sortArr);
        if ($sortArrLength <= 1) return $sortArr;
        $compareValue = $sortArr[0];
        $right = $left = [];
        for ($i = 1; $i < $sortArrLength; $i++) {
            if ($sortArr[$i] > $compareValue) {
                $left[] = $sortArr[$i];
            }
            if ($sortArr[$i] < $compareValue) {
                $right[] = $sortArr[$i];
            }
        }
        $right = $this->quickSort($right);
        $left  = $this->quickSort($left);
        return array_merge($left, [$compareValue], $right);
    }

    /**
     * 是否是有效括号
     * @param $brackets
     * @return bool
     */
    public function isAvoidBrackets($brackets): bool
    {
        $bracketsLen = strlen($brackets);
        //括号长度是0和奇数false
        if (!$bracketsLen || $bracketsLen & 1) return false;

        $bracketsArr = [
            ')' => '(',
            '}' => '{',
            ']' => '[',
        ];
        //声明栈
        $stack = [];
        for ($i = 0; $i < $bracketsLen; $i++) {
            if (isset($bracketsArr[$brackets[$i]])) {
                //栈是空或出栈元素不等于$bracketsArr[i]返回false
                if (empty($stack) || array_pop($stack) != $bracketsArr[$brackets[$i]]) return false;
                continue;
            }
            //入栈
            $stack[] = $brackets[$i];
        }
        return !count($stack);
    }

    /**
     * 冒泡排序
     * @param $bubblingArr
     * @return mixed
     */
    public function bubblingSort($bubblingArr)
    {
        if (empty($bubblingArr) || !is_array($bubblingArr)) return $bubblingArr;
        for ($i = 0; $i < count($bubblingArr); $i++) {
            for ($j = 0; $j < count($bubblingArr) - $i - 1; $j++) {
                if ($bubblingArr[$j] > $bubblingArr[$j+1]) {
                    $tempElement       = $bubblingArr[$j+1];
                    $bubblingArr[$j+1] = $bubblingArr[$j];
                    $bubblingArr[$j]   = $tempElement;
                }
            }
        }
        return $bubblingArr;
    }

    /**
     * 合并两个有序数组
     * @param array $arr1
     * @param array $arr2
     * @return array
     */
    public function mergeSortedArray(array $arr1, array $arr2): array
    {
        $sortedArr = [];
        while (!empty($arr1) && !empty($arr2)) {
            $shiftArr1 = array_shift($arr1);
            $shiftArr2 = array_shift($arr2);
            if ($shiftArr1 >= $shiftArr2) {
                $sortedArr[] = $shiftArr2;
                array_unshift($arr1, $shiftArr1);
                continue;
            }
            $sortedArr[] = $shiftArr1;
            array_unshift($arr2, $shiftArr2);
        }
        return array_merge($sortedArr, empty($arr1) ? $arr2 : $arr1);
    }

    /**
     * 交换两个数
     * @param $one
     * @param $two
     * @return string
     */
    public function changeTowNumber($one, $two): string
    {
        $one = $one + $two;
        $two = $one - $two;
        $one = $one - $two;
        return $one . '-' . $two;
    }

    /**
     * 两个数之和
     * @param array $array
     * @param int $target
     * @return false|string
     */
    public function towNumberSum(array $array, int $target)
    {
        foreach ($array as $k => $v) {
            if (isset($hashTable[$target-$v])) {
                return $k . $hashTable[$target-$v];
            }
            $hashTable[$v] = $k;
        }
        return false;
    }

    public function largeNumberSum($one, $two)
    {

    }

    /**是否是回文字符串
     * @param string $palindrome
     * @return bool
     */
    public function isPalindrome(string $palindrome)
    {
        //12321
        $palindrome = preg_replace('/[^a-z0-9]/i', '', strtolower($palindrome));
        $len = strlen($palindrome);
        if ($len < 1) return false;
        for ($i = 0; $i < $len/2; $i++) {
            if ($palindrome[$i] != $palindrome[$len - $i -1]) {
                return false;
            }
        }
        return true;
    }

    /**
     * 寻找最长不重复子串
     * @return void
     */
    public function findNotRepeatMaxStr()
    {
        $str  = 'yes你是一个天才少年呢!';
        $start = $maxLen = 0;
        $len = strlen($str);
        $map = [];
        for ($i = 0; $i < $len; $i++) {

        }
    }
}